#include <stdio.h>
#include <stdlib.h>
#include "list.h"

void init_list(struct list ** list)
{
  *list = malloc(sizeof(struct list));
  if (list == NULL)
    printf("init_list malloc fail.\n");
  
  (*list)->num = 0;
  (*list)->next = NULL;
}

unsigned int length(struct list ** node)
{
  struct list * src;
  int len;

  src = * node;
  while (src != NULL) {
    len++;
    src = src->next;
  }

  return len;
}

int empty(struct list ** node)
{
  struct list * src;

  src = * node;

  if (src != NULL)
    return 1;
  else
    return 0;
}

void clean_list(struct list ** node)
{
  struct list * src, * des;

  src = * node;
  while (src != NULL) {
    des = src->next;
    free(src);
    src = des;
  }
}

void display(struct list ** node)
{
  struct list * src;
  int i;
 
  src = * node;
  while (src) {
    printf(" %d ", src->num);
    src = src->next;
  }

  printf("\n");
}

void putout(struct list * node)
{
  struct list * src;

  if (!node)
    return;
  
  src = node->next; // 会屏蔽掉第一节点，适合有头结点的链表
  while (src) {
    printf(" %d ", src->num);
    src = src->next;
  }
  printf("\n\n");
}

void insert_head(struct list ** node, int value)
{
  struct list * des;

  des = (struct list *) malloc(sizeof(struct list));
  if (des == NULL) {
    printf("insert head malloc fail.\n");
    return ;
  }
  des->num = value;
  des->next = * node;
  * node = des;
}

void insert_tail(struct list ** node, int value)
{
  struct list * src, * des;

  des = (struct list *) malloc(sizeof(struct list));
  if (des == NULL) {
    printf("insert tail malloc fail.\n");
    return ;
  }
  des->num = value;
  des->next = NULL;

  src = * node;
  if (* node == NULL) // 空
    * node = des;
  else {
    while (src->next != NULL) // 非空
      src = src->next; // 移到最后
    src->next = des;   // 在插入
  }
}

int insert_pos_head(struct list ** node, int value, int position)
{
  struct list * src , * des,  * n, * p;
  int pos;

  src = * node;
  if (src == NULL)
    return -1;

  if (length(node) < position) {
    printf("position too long!\n");
    return -1;
  }

  des = (struct list *) malloc(sizeof(struct list));
  if (des == NULL) {
    printf("insert position head malloc fial.\n");
    return -1;
  }
  des->num = value;
  des->next = NULL;

  pos = 0;
  while (src != NULL) {
    pos++;
    p = src;
    src = src->next;
    n = src;
    if (pos == position-1) { // 不-1 就插到后面了。
      p->next = des;
      des->next = n;
      break;
    }
  }

  return 0;
}


int insert_pos_tail(struct list ** node, int value, int position)
{
  struct list * src , * des,  * n;
  int pos;

  src = * node;
  if (src == NULL)
    return -1;

  if (length(node) < position) {
    printf("position too long!\n");
    return -1;
  }

  des = (struct list *) malloc(sizeof(struct list));
  if (des == NULL) {
    printf("insert position head malloc fial.\n");
    return -1;
  }
  des->num = value;
  des->next = NULL;

  pos = 0;
  while (src != NULL) {
    pos++;
    src = src->next;
    n = src;
    if (pos == position-1) { 
      des->next = n->next;  // 指向 src 下一个结构体
      n->next = des;        // 把des 赋给当前 src 的成员 next
      break;
    }
  }

  return 0;
}

int delete_from_value(struct list ** node, int value)
{
  struct list * src, * cur;

  src = * node;
  cur = NULL;
  while (src != NULL) {
    if (src->num == value) {
      break;      
    }
    cur = src;
    src = src->next;
  }

  if (cur == NULL)
    * node = (* node)->next;  // 第一个值为删除值，指针后移， src 指向起始，故释放它
  else
    cur->next = src->next;

  free(src);
  
  return 0;
}

void delete_position(struct list ** node, int position)
{
  struct list * src, * cur;
  int pos;

  src = * node;
  if (src == NULL || position <= 0) {
    printf("node is null and position is zero.\n");
    return ;
  }

  pos = 0;
  while (src != NULL) {
    pos++;
    if (pos == position)
      break;
    cur = src;
    src = src->next;
  }
  
  if (src == NULL) {
    printf("position value is error.\n");
    return ;
  }

  if (position == 1) 
    * node = (* node)->next;  // 指针后移， src 指向起始，故释放它
  else
    cur->next = src->next;
  
  free(src);
}

void delete_head(struct list ** node)
{
  struct list * src;

  src = * node;
  if (src == NULL) {
    printf("list is empty.\n");
    return ;
  }
  
  * node = (* node)->next;   // 指针后移， src 指向起始，故释放它
  free(src);
}

void delete_tail(struct list ** node)
{
  struct list * src, * des;

  src = * node;
  des = NULL;
  if (src == NULL) {
    printf("list is empty.\n");
    return ;
  }

  while (src->next != NULL) {
    des = src;  // 指向了最后
    src = src->next;
  }

  if (des == NULL)
    * node = NULL;
  else
    des->next = NULL;

  free(src);
}

void reverse(struct list * node)
{
  struct list * src, * des;

  src = node->next;  // 指向第二个数据节点
  node->next = NULL; // 将原链表置为空
  
  while (src) {
    des = src;
    src = src->next;
    des->next = node->next; // 将当前节点插到头节点的后面
    node->next = des;
   }
}

struct list * reverse_perfect_return(struct list * node)
{
  struct list * src, * des;

  src = node;
  node = NULL;

  while (src) {
    des = src;
    src = src->next;
    des->next = node;
    node = des;
  }

  return node;
}

void  reverse_perfect(struct list ** node)
{
  struct list * src, * des;

  src = * node;  // 指向第一个结点
  * node = NULL; // 目前，链表node为空 (num, next 都为空)

  while (src) {
    des = src;          // des 指向要翻转的结点
    src = src->next;    // 指向下一个要翻转的结点
    des->next = * node; // 链接到翻转后的链表
    * node = des;       // 为链接下一个做准备
  }
}

void reverse_dis(struct list * node)
{
  printf("1th - level : node Address: %p\n", node);

  if (node != NULL) {
    reverse_dis(node->next);
    printf(" %d", node->num);
  }
  printf("\n");
  printf("2th - level : node Address: %p\n", node);
}

struct list * merge(struct list * first, struct list * second)
{
  struct list * src;

  src = first;
  while (src->next)  // 改为 src, 循环多一次，地址会跑飞，因而链不起来
    src = src->next;
  
  src->next = second;

  return first;
}

struct list * merge_sort_recursion(struct list * first, struct list * second)
{
  struct list * src;

  if (first == NULL)
    return second;
  else if (second == NULL)
    return first;

  src = NULL;
  if (first->num < second->num) {
    src = first;
    src->next = merge_sort_recursion(first->next, second);
  }
  else {
    src = second;
    src->next = merge_sort_recursion(first, second->next);
  }

  return src;
}

struct list * merge_sort_(struct list * first, struct list * second)
{
  struct list * src, * pfirst, * psecond, * des;

  src = first;
  des = first;
  pfirst = first;
  psecond = second;

  while (pfirst && psecond) {
    if (pfirst == psecond) {
      psecond = NULL;
      break;
    }
    else if (pfirst->num > psecond->num) {
      des->next = psecond;
      psecond = psecond->next;
      des = des->next;
      des->next = pfirst;
    }
    else {
      if (pfirst->next == psecond->next) {
	psecond->next = NULL;
      }
      des = pfirst;
      pfirst = pfirst->next;
    }
  }

  des->next = pfirst ? pfirst : psecond;

  return src;
}

struct list * merge_sort(struct list * first, struct list * second)
{
  struct list * head, * src;

  if (first == NULL || first->next == NULL)
    return second;
  if (second == NULL || second->next == NULL)
    return first;

  head = (struct list *)malloc(sizeof(struct list));
  src = NULL;

  if (first != NULL && second != NULL) {
    if (first->num <= second->num) {
      head->next = first;
      first = first->next;
    }
    else {
      head->next = second;
      second = second->next;
    }
  }
   
  src = head->next;

  while (first != NULL && second != NULL) {
    if (first->num <= second->num) {
      src->next = first;
      first = first->next;
      src = src->next;
     }
    else {
      src->next = second;
      second = second->next;
      src = src->next;
    }
  }

  while (first != NULL) {
    src->next = first;
    first = first->next;
    src = src->next;
  }

  while (second != NULL) {
    src->next = second;
    second = second->next;
    src = src->next;
  }  

  return head;
}

int main(void)
{
  struct list * node, * cur;
  struct list * first, * second;

  #if 0
  // init_list(& node); // 带表头，即多出一个初始化时设置为空的结构体。
  node = NULL;   // 不带表头
  insert_head(& node, 1); 
  insert_head(& node, 2); 
  insert_head(& node, 3); 
  insert_head(& node, 4); 
  insert_head(& node, 5);
  display(& node);  // 5 4 3 2 1
  clean_list(& node);
  
  node = NULL;
  insert_tail(& node, 1); 
  insert_tail(& node, 2); 
  insert_tail(& node, 3); 
  insert_tail(& node, 4); 
  insert_tail(& node, 5);

  display(& node); //  1 2 3 4 5

  insert_pos_head(& node, 8, 3);  
  display(& node); //  1 2 8 3 4 5

  delete_from_value(& node, 8);   
  display(& node); //  1 2 3 4 5

  insert_pos_tail(& node, 9, 3);  
  display(& node); //  1 2 3 9 4 5

  delete_from_value(& node, 9);   
  display(& node); //  1 2 3 4 5

  clean_list(& node);
  #endif

  #if 0
  node = NULL;
  printf("\n################# delete position ################\n");
  insert_tail(& node, 1); 
  insert_tail(& node, 2); 
  insert_tail(& node, 3); 
  insert_tail(& node, 4); 
  insert_tail(& node, 5);
  display(& node); //  1 2 3 4 5

  delete_position(& node, 1);  
  display(& node);  // 2 3 4 5

  delete_head(& node);         
  display(& node);  // 3 4 5

  delete_tail(& node);         
  display(& node);  // 3 4

  insert_tail(& node,6);       
  display(& node);  // 3 4 6
  clean_list(& node);
  #endif 

#if 0
  node = NULL;
  printf("\n################# reverse  ################\n");
  insert_tail(& node, 61); 
  insert_tail(& node, 62); 
  insert_tail(& node, 63); 
  insert_tail(& node, 64); 
  insert_tail(& node, 65);
  display(& node); //  61 62 63 64 65

  #if 0
  reverse_dis(node);  
  display(& node);  // 61 62 63 64 65
  #endif

  #if 0
  reverse(node);  
  display(& node); // 61  65  64  63  62
  #endif

  #if 0
  cur = reverse_debug(node);  
  display(& cur);  // 61 65 64 63 62                              
  display(& node); // 61 65 64 63 62
  #endif

  #if 0
  printf("%p:%p:%p:%p:%p\n", node, node->next, node->next->next, node->next->next->next, node->next->next->next->next);
  cur = reverse_debug(node);  // 单指针，不需要返回值，是因为头节点一直在
  display(& cur);  // 61 65 64 63 62
  display(& node); // 61 65 64 63 62
  #endif

  #if 0
  printf("%p:%p:%p:%p:%p\n", node, node->next, node->next->next, node->next->next->next, node->next->next->next->next);
  cur = reverse_perfect_debug(node); // 单指针，需要返回值
  printf("cur=reverse_perfect_debug(node) %p:%p:%p\n", cur, node, node->next);  
  display(& cur);  // 65 64 63 62 61
  display(& node); // 61
  #endif

  #if 0
  printf("%p:%p \n", (void *)node, *node);
  printf("%p:%p:%p:%p:%p\n", node, node->next, node->next->next, node->next->next->next, node->next->next->next->next);
  reverse_perfect_noreturn_debug(& node); // 双指针，不需要返回值
  display(& node); // 61
  #endif

  #if 0
  reverse_perfect(& node);  // 双指针，不需要返回值
  display(& node); // 65 64 63 62 61
  #endif

  #if 0
  cur = reverse_1(node);  
  display(& cur);  
  display(& node);
  #endif

  #if 0
  cur = reverse_2(node);  
  display(& cur);  
  display(& node);
  #endif
  clean_list(& node);
#endif 

#if 1
  printf("\n################# merge  ################\n");
  #if 0
  first = second = NULL;
  insert_tail(& first, 61); 
  insert_tail(& first, 62); 
  insert_tail(& first, 63); 
  insert_tail(& first, 64); 
  insert_tail(& first, 65);
  display(& first);

  insert_tail(& second, 71); 
  insert_tail(& second, 72); 
  insert_tail(& second, 73); 
  insert_tail(& second, 74); 
  insert_tail(& second, 75);
  display(& second);

  cur = merge(first, second);  
  display(& cur);  // putout(first);
  clean_list(& first);  
  clean_list(& second);
  #endif
  #if 1
  first = second = NULL;
  insert_tail(& first, 61); 
  insert_tail(& first, 72); 
  insert_tail(& first, 78); 
  insert_tail(& first, 84); 
  insert_tail(& first, 95);
  display(& first);

  insert_tail(& second, 31); 
  insert_tail(& second, 662); 
  insert_tail(& second, 83); 
  insert_tail(& second, 94); 
  insert_tail(& second, 105);
  insert_tail(& second, 5);
  display(& second);

  cur = merge_sort_recursion(first, second);		// recursion   不完善
  //cur = merge_sort(first, second);  // 不完善
  //cur = merge_sort_(first, second); // 有错误
  display(& cur);

  clean_list(& first);  
  clean_list(& second);
  #endif
#endif

  return 0;
}




 
